package lc20240701;

import java.util.Arrays;

public class LongestIncreasingSubsequence {

    /**
     * 找到整数数组 nums 中最长严格递增子序列的长度
     * @param nums 输入的整数数组
     * @return 最长严格递增子序列的长度
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1); // 初始时，每个元素都可以单独成为子序列，因此长度为 1

        int maxLength = 1; // 用于记录最长的子序列长度

        // 遍历数组
        for (int i = 1; i < nums.length; i++) {
            // 对于每个 nums[i]，查找之前的元素 nums[j]
            for (int j = 0; j < i; j++) {
                // 如果 nums[i] > nums[j]，说明可以构成递增子序列
                if (nums[i] > nums[j]) {
                    // 更新 dp[i] 的值，取当前 dp[i] 和 dp[j] + 1 的较大值
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 更新最长子序列的长度
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
        
        // 示例 1
        int[] nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Length of LIS: " + lis.lengthOfLIS(nums1)); // 输出: 4 (最长子序列是 [2, 3, 7, 18])
        
        // 示例 2
        int[] nums2 = {0, 1, 0, 3, 2, 3};
        System.out.println("Length of LIS: " + lis.lengthOfLIS(nums2)); // 输出: 4 (最长子序列是 [0, 1, 2, 3])
        
        // 示例 3
        int[] nums3 = {7, 7, 7, 7, 7, 7, 7};
        System.out.println("Length of LIS: " + lis.lengthOfLIS(nums3)); // 输出: 1 (最长子序列是 [7])
    }
}
